/** tomasulo_main.cpp
  * tomasulo pipelined processor
  * Author: Long Tran
  * Email:  ltran3@gatech.edu
  * Date created: Mar 19 2011
  */

#include <iostream>
#include <fstream>
#include <sstream>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>

int global_time = 0;
std::ofstream logfile("LOG");

typedef unsigned int uint;
#define N_TYPE 3

class Instruction
{
  int tag_;                      // id (and dest tag)
  uint addr_;                    // address
  int type_;                     // function unit type (-1 for invalid instruction)
  int dest_, src1_, src2_;       // dest, srs1, src2 registers
  int src1Tag_, src2Tag_;        // src1, src2 tag
  bool src1Ready_, src2Ready_;   // ready bits

  // timing information
  int fetchTime_;
  int dispatchTime_;
  int scheduleTime_;
  int executeTime_;
  int updateTime_;

  static int currentTag_;        // counting variable (to generate unique tag)
public:
  Instruction()
    : tag_(-1), dest_(-1),
      src1_(-1), src2_(-1), src1Tag_(-1), src2Tag_(-1), src1Ready_(false), src2Ready_(false),
      fetchTime_(-1), dispatchTime_(-1), scheduleTime_(-1), executeTime_(-1), updateTime_(-1)
  {}
  /** read instruction from stream in format: addr type dest src1 src2 */
  void read(std::istream& input) {
    std::string line;
    std::getline(input, line);
    if (line.empty()) {
      type_ = -1; // no more instruction from input
      return;
    }
    std::stringstream s(line);
    tag_ = currentTag_++;
    s >> std::hex >> addr_ >> std::dec >> type_ >> dest_ >> src1_ >> src2_;
    fetchTime_ = global_time;
    dispatchTime_ = global_time+1;
  }

  /** getters */
  int tag() const { return tag_; }
  uint addr() const { return addr_; }
  int type() const { return type_; }
  int dest() const { return dest_; }
  int src1() const { return src1_; }
  int src2() const { return src2_; }
  int src1Tag() const { return src1Tag_; }
  void set_src1Tag(int src1Tag) { src1Tag_ = src1Tag; }
  int src2Tag() const { return src2Tag_; }
  void set_src2Tag(int src2Tag) { src2Tag_ = src2Tag; }
  bool src1Ready() const { return src1Ready_; }
  void set_src1Ready(bool src1Ready) { src1Ready_ = src1Ready; }
  bool src2Ready() const { return src2Ready_; }
  void set_src2Ready(bool src2Ready) { src2Ready_ = src2Ready; }
  int fetchTime() const { return fetchTime_; }
  int dispatchTime() const { return dispatchTime_; }
  int scheduleTime() const { return scheduleTime_; }
  void set_scheduleTime(int scheduleTime) { scheduleTime_ = scheduleTime; }
  int executeTime() const { return executeTime_; }
  void set_executeTime(int executeTime) { executeTime_ = executeTime; }
  int updateTime() const { return updateTime_; }
  void set_updateTime(int updateTime) { updateTime_ = updateTime; }
  static void resetCounter() { global_time = 0; currentTag_ = 0; }
};

int Instruction::currentTag_ = 0;

class Program : public std::vector<Instruction>
{
  int verbose_;
public:
  Program(int verbose = 0) : verbose_(verbose) {}
  int getNext(std::istream& input) {
    push_back(Instruction());
    back().read(input);
    if (back().type() == -1) {
      this->pop_back();
      if (verbose_) logfile << "end of input\n";
      return -1;
    }
    else {
      if (verbose_) logfile << std::dec << global_time
          << " fetch " << std::dec << back().tag() << " "
          << std::hex << back().addr() << " "
          << std::dec << back().type() << " "
          << back().dest() << " "
          << back().src1() << " "
          << back().src2() << "\n";
      return size()-1;
    }
  }
  /** print all logs */
  void output() {
    std::cout << "INST\tFETCH\tDISP\tSCHED\tEXEC\tSTATE\n";
    for (uint i = 0; i < size(); i++) {
      std::cout << std::dec
                << at(i).tag() << "\t"
                << at(i).fetchTime() << "\t"
                << at(i).dispatchTime() << "\t"
                << at(i).scheduleTime() << "\t"
                << at(i).executeTime() << "\t"
                << at(i).updateTime() << "\n";
    }
  }
};

/** dispatch queue is a list of instruction id
 *  of which -1 means an empty slot
 */
class DispatchQ : public std::vector<int>
{
  typedef std::vector<int>      __Base;
protected:
  Program* program_;
  int verbose_;
  std::queue<int> emptySlot_;
public:
  DispatchQ(Program& program, int size, int verbose = 0)
    : __Base(size, -1), program_(&program), verbose_(verbose)
  {}
  bool isEmpty(uint slot) { return slot >= 0 && slot < size() && this->at(slot) == -1; }
  /** access i-th instruction */
  Instruction& instRef(uint i) { assert(i >= 0 && i < size()); return program_->at(this->at(i)); }
  const Instruction& inst(uint i) const { assert(i >= 0 && i < size()); return program_->at(this->at(i)); }

  /** clear a slot in the queue */
  void clearSlot(uint i) { assert(i >= 0 && i < size()); this->at(i) = -1; }
  void markEmptySlots() {
    emptySlot_ = std::queue<int>();
    for (uint i = 0; i < size(); i++) if (isEmpty(i)) emptySlot_.push(i);
  }

  /** Fetch up to N instructions from input stream to empty slots */
  bool fetch(std::istream& input, int N) {
    if (emptySlot_.empty()) return false;
    for (int k = 0; k < N && !emptySlot_.empty(); k++) {
      int inst_id = program_->getNext(input);
      if (inst_id != -1) {               // successfully get an instruction
        int slot = emptySlot_.front(); emptySlot_.pop();
        this->at(slot) = inst_id;
      }
    }
    return true;
  }

  bool emptyQueue() {
    for (uint i = 0; i < size(); i++) if (this->at(i) != -1) return false;
    return true;
  }

  /** dump queue entries */
  void dump() {
    for (uint i = 0; i < size(); i++) {
      logfile << "[" << std::dec << i << "] = ";
      if (isEmpty(i)) {
        logfile << "empty";
      }
      else {
        logfile << inst(i).tag() << " time = " << inst(i).dispatchTime();
      }
      logfile << "\n";
    }
  }
};

/** Processor's registers */
class Register
{
  int id_;            // Register number
  bool ready_;        // ready bit
  int tag_;           // current tag
public:
  Register(int id = 0)
  : id_(id), ready_(true), tag_(-1) {}

  /** Assign new tag to a register */
  void newTag(int tag) { ready_ = false; tag_ = tag; }

  /** When a register is ready in result bus */
  void ready(int tag) { if (tag_ == tag) ready_ = true; }

  /** getters */
  bool isReady() const { return ready_; }
  int tag() const { return tag_; }

  /** This should be the same as array index of register file */
  int regNo() const { return id_; }
};

class RegisterFile : public std::vector<Register>
{
  int verbose_;
public:
  RegisterFile(int verbose = 0) : verbose_(verbose) {}

  /** Populate tagging information from register file to scheduling queue entry
   *  and assign new tag to the destination register
   */
  void processTag(Instruction& inst) {
    if (verbose_) logfile << std::dec << global_time
        << " check regfile dest = " << std::dec << inst.dest();
        //<< " src1 = " << inst.src1() << " src2 = " << inst.src2() << "\n";
    // check src1
    if (verbose_) logfile << " src1=" << inst.src1();
    if (inst.src1() == -1 || this->at(inst.src1()).isReady()) {
      inst.set_src1Ready(true);
      if (verbose_) logfile << " (1)";
    }
    else {
      inst.set_src1Ready(false);
      inst.set_src1Tag(this->at(inst.src1()).tag());
      if (verbose_) logfile << " (0)";
    }

    // check src2
    if (verbose_) logfile << " src2=" << inst.src2();
    if (inst.src2() == -1 || this->at(inst.src2()).isReady()) {
      inst.set_src2Ready(true);
      if (verbose_) logfile << " (1)";
    }
    else {
      inst.set_src2Ready(false);
      inst.set_src2Tag(this->at(inst.src2()).tag());
      if (verbose_) logfile << " (0)";
    }

    // set DestReg.tag
    if (inst.dest() != -1)
      this->at(inst.dest()).newTag(inst.tag());
    if (verbose_) logfile << "\n";
  }
};

class SchedQ : public DispatchQ
{
  RegisterFile* regFile_;        // needed to access register file
  int type_;                     // function unit type
public:
  SchedQ(Program& program, RegisterFile& regFile, int size, int type, int verbose = 0)
    : DispatchQ(program, size, verbose), regFile_(&regFile), type_(type)
  {}

  bool dispatch(int id) {
    if (emptySlot_.empty()) return false;
    if (verbose_) logfile << std::dec << global_time << " dispatch " << id << "\n";
    int slot = emptySlot_.front(); emptySlot_.pop();
    this->at(slot) = id;
    Instruction& inst = program_->at(id);
    inst.set_scheduleTime(global_time+1);
    regFile_->processTag(inst);
    return true;
  }

  void update(int slot, int tag, int time) {
    if (isEmpty(slot)) return;
    Instruction& inst = instRef(slot);
    if (inst.scheduleTime() > global_time) return;    // result available before dispatch time, the instruction is not in schedule queue yet
    if (!inst.src1Ready() && inst.src1Tag() == tag) {
      inst.set_src1Ready(true);
      if (verbose_) logfile << std::dec << global_time
          << " update type="<< type_ << " slot=" << slot << " src1 tag=" << std::dec << inst.tag() << "\n";
    }
    if (!inst.src2Ready() && inst.src2Tag() == tag) {
      inst.set_src2Ready(true);
      if (verbose_) logfile << std::dec << global_time
          << " update type="<< type_ << " slot=" << slot << " src2 tag=" << std::dec << inst.tag() << "\n";
    }
  }

  /** dumping entries' information */
  void dump() {
    for (uint i = 0; i < size(); i++) {
      logfile << "[" << std::dec << i << "] = ";
      if (isEmpty(i)) logfile << "empty";
      else {
        logfile << inst(i).tag() << " sched time = " << inst(i).scheduleTime()
                  << " type=" << inst(i).type()
                  << " src1=[" << inst(i).src1() << " " << inst(i).src1Ready() << " " << inst(i).src1Tag() << "]"
                  << " src2=[" << inst(i).src2() << " " << inst(i).src2Ready() << " " << inst(i).src2Tag() << "]"
                  << " dest=[" << inst(i).dest() << " " << inst(i).tag() << "] ";
        if (inst(i).executeTime() == -1)
          logfile << "---------";
        else if (inst(i).updateTime() != -1)
          logfile << "exec done " << inst(i).updateTime();
        else
          logfile << "executing " << inst(i).executeTime();
      }
      logfile << "\n";
    }
  }
};

/** The function unit - FUs */
class FunctionUnit : public std::queue<int>
{
  Program* program_;          // needed to access instruction
  int type_;                  // function unit type
  int cycle_;                 // number of cycles needed
  int verbose_;
public:
  FunctionUnit(Program& program, int type, int cycle, int verbose = 0)
    : program_(&program), type_(type), cycle_(cycle), verbose_(verbose) {}

  /** getters */
  int type() const { return type_; }
  int cycle() const { return cycle_; }
  bool isAvailable() const {
    // type 0 is unpipelined
    // other types are pipelined, always available at beginning of cycle
    return type_ != 0 ? true : empty();
  }

  /** fire (issue) i-th instruction of the program */
  void fire(int id) {
    Instruction& inst = program_->at(id);
    inst.set_executeTime(global_time+1);
    push(id);
    if (verbose_) logfile << std::dec << global_time << " schedule " << id << "\n";
  }
};

/** Result bus */
class CDB
{
public:
  int tag_;    // tag
  int reg_;    // register id
  int time_;   // issue time
  CDB(int tag = -1, int reg = -1, int time = -1) : tag_(tag), reg_(reg), time_(time) {}
};

struct QueueEntry {
  int tag_, slot_, type_;
  QueueEntry() {}
  QueueEntry(int tag, int slot) : tag_(tag), slot_(slot) {}
  QueueEntry(int tag, int slot, int type) : tag_(tag), slot_(slot), type_(type) {}
  bool operator()(const QueueEntry& e1, const QueueEntry& e2) const {
    return e1.tag_ < e2.tag_;
  }
};

class Processor
{
  std::istream& input_;
  int k0_, k1_, k2_, D_, m_, N_, verbose_;
  Program prog_;
  DispatchQ dq_;
  RegisterFile regFile_;
  std::vector<SchedQ> sq_;
  std::vector<std::vector<FunctionUnit> > fu_;
  std::vector<CDB> cdb_;
public:
  double ipc_;
public:
  Processor(std::istream& input, int k0, int k1, int k2, int D, int m, int N, int verbose)
  : input_(input), k0_(k0), k1_(k1), k2_(k2), D_(D), m_(m), N_(N), verbose_(verbose),
    prog_(verbose), dq_(prog_, D, verbose), regFile_(verbose), fu_(N_TYPE)
  {
    for (int i = 0; i < 128; i++)
      regFile_.push_back(Register(i));    // initialize register file (all registers are ready)
    sq_.push_back(SchedQ(prog_, regFile_, m*k0, 0, verbose));
    sq_.push_back(SchedQ(prog_, regFile_, m*k1, 1, verbose));
    sq_.push_back(SchedQ(prog_, regFile_, m*k2, 2, verbose));

    fu_[0] = std::vector<FunctionUnit>(k0, FunctionUnit(prog_, 0, 1, verbose));
    fu_[1] = std::vector<FunctionUnit>(k1, FunctionUnit(prog_, 1, 2, verbose));
    fu_[2] = std::vector<FunctionUnit>(k2, FunctionUnit(prog_, 2, 3, verbose));
  }

  int infiniteLoop() {
    while (1) {
      // mark empty slots of the queues
      dq_.markEmptySlots();
      for (int type = 0; type < N_TYPE; type++) {
        sq_[type].markEmptySlots();
        //if (verbose_) 
        //  for (uint i = 0; i < sq_[type].size(); i++) if (sq_[type][i] == -1) 
        //    logfile << std::dec << global_time << " empty type=" << type << " slot=" << i << "\n";
      }
      // clear old result buses
      std::vector<CDB> tmp = cdb_;
      cdb_.clear();
      for (uint i = 0; i < tmp.size(); i++)
        if (tmp[i].time_ >= global_time-2) cdb_.push_back(tmp[i]);

      removeDoneInst();
      execute();

      // gather available function units
      std::vector<std::queue<int> > availFU(N_TYPE);
      for (int type = 0; type < N_TYPE; type++)
        for (uint k = 0; k < fu_[type].size(); k++)
          if (fu_[type][k].isAvailable()) {
            availFU[type].push(k);
            if (verbose_) logfile << std::dec << global_time << " fu available type=" << type << " id=" << k << "\n";
          }
      schedule(availFU);
      updateSchedQ();               // order of state update here is important
      updateRegFile();              // register file is updated just before dispatch
      dispatch();
      dq_.fetch(input_, N_);

      if (verbose_) dump();

      global_time++;

      if (input_.eof() && dq_.emptyQueue() &&
          sq_[0].emptyQueue() && sq_[1].emptyQueue() && sq_[2].emptyQueue()) break;
    }
    ipc_ = (double) prog_.size() / (global_time-1);
    return 0;
  }

  void output() {
    std::cout << std::dec << "N = " << N_ << " m = " << m_ << " D = " << D_ 
              << " k0 = " << k0_ << " k1 = " << k1_ << " k2 = " << k2_ << "\n";
    prog_.output();

    std::cout << "\nAvg inst fired per cycle: " << ipc_ << "\n";
    std::cout << "Total instructions: " << prog_.size() << "\n";
    std::cout << "Total run time (cycles): " << global_time-1 << "\n";
    std::cout << "Avg IPC: " << ipc_ << "\n";
  }

  void dispatch() {
    std::vector<QueueEntry> entries;
    for (uint i = 0; i < dq_.size(); i++) if (!dq_.isEmpty(i)) {
      int inst_id = dq_[i];
      const Instruction& inst = prog_[inst_id];
      if (inst.dispatchTime() <= global_time) entries.push_back(QueueEntry(inst.tag(), i));
    }
    std::sort(entries.begin(), entries.end(), QueueEntry());  // sort instructions by tags
    for (uint i = 0; i < entries.size(); i++) {
      int slot = entries[i].slot_;
      int inst_id = dq_[slot];
      const Instruction& inst = prog_[inst_id];
      if (sq_[inst.type()].dispatch(inst_id))  // successfully dispatch
        dq_.clearSlot(slot);
      else
        break;                                 // stall because we have to dispatch in order
    }
  }

  void schedule(std::vector<std::queue<int> >& availFU) {
    std::vector<QueueEntry> entries;
    for (int type = 0; type < N_TYPE; type++)
      for (uint slot = 0; slot < sq_[type].size(); slot++) if (!sq_[type].isEmpty(slot)) {
        int inst_id = sq_[type][slot];
        const Instruction& inst = prog_[inst_id];
        if (inst.scheduleTime() <= global_time && inst.executeTime() == -1 &&
            inst.src1Ready() && inst.src2Ready()) {  // not fired, independent instruction
          entries.push_back(QueueEntry(inst.tag(), slot, inst.type()));
        }
      }
    std::sort(entries.begin(), entries.end(), QueueEntry());  // sort instructions by tags

    for (uint i = 0; i < entries.size(); i++) {
      int slot = entries[i].slot_;
      int type = entries[i].type_;
      int inst_id = sq_[type][slot];
      if (availFU[type].empty()) continue; // no available FU of needed type
      int fu_id = availFU[type].front(); availFU[type].pop();
      fu_[type][fu_id].fire(inst_id);
    }
  }

  void execute() {
    for (int type = 0; type < N_TYPE; type++)
      for (uint k = 0; k < fu_[type].size(); k++) {
        FunctionUnit& f = fu_[type][k];
        if (f.empty()) continue;
        int inst_id = f.front();
        Instruction& inst = prog_[inst_id];
        if (inst.executeTime() + f.cycle() - 1 <= global_time) { // execution should end in this cycle
          inst.set_updateTime(global_time+1);
          f.pop(); // remove instruction from execution pipeline
          cdb_.push_back(CDB(inst.tag(), inst.dest(), global_time+1)); // output to CDB
        }
      }
  }

  void updateSchedQ() {
    for (uint i = 0; i < cdb_.size(); i++) if (cdb_[i].time_ <= global_time) {
      for (int type = 0; type < N_TYPE; type++)
        for (uint slot = 0; slot < sq_[type].size(); slot++)
          sq_[type].update(slot, cdb_[i].tag_, cdb_[i].time_);
    }
  }

  void updateRegFile() {
    for (uint i = 0; i < cdb_.size(); i++) if (cdb_[i].reg_ != -1 && cdb_[i].time_ <= global_time) {
      int tag = cdb_[i].tag_;
      int reg = cdb_[i].reg_;
      int time = cdb_[i].time_;
      if (verbose_) logfile << std::dec << global_time
          << " update reg = " << std::dec << reg << " tag = " << tag << " time = " << time << "\n";
      regFile_[reg].ready(tag);
    }
  }

  void removeDoneInst() {
    for (int type = 0; type < N_TYPE; type++)
      for (uint slot = 0; slot < sq_[type].size(); slot++) if (!sq_[type].isEmpty(slot)) {
        const Instruction& inst = sq_[type].inst(slot);
        if (inst.updateTime() != -1 && inst.updateTime() <= global_time) {
          sq_[type].clearSlot(slot);
          if (verbose_) logfile << std::dec << global_time << " clear type=" << type << " slot=" << slot << "\n";
        }
      }
  }

  void dump() {
    logfile << "----- " << std::dec << global_time << " processor dump *****\n";
    logfile << "++dispQ " << "\n";
    dq_.dump();
    for (int type = 0; type < N_TYPE; type++) {
      logfile << "--schedQ " << type << "\n";
      sq_[type].dump();
    }
    logfile << "-----\n";
    logfile.flush();
  }
};

void process_parameter(int argc, char** argv, int &k0, int &k1, int &k2, int &D, int &m, int &N, std::string& fName);
void try_all(const std::string& fName);

int main(int argc, char** argv)
{
  //std::cout << "Tomasulo pipelined processor ... simulating\n";
  if (argc == 2) {  // try all parameter
    try_all(argv[1]);
    return 0;
  }

  int k0, k1, k2, D, m, N;
  std::string fName;
  std::ifstream f;

  process_parameter(argc, argv, k0, k1, k2, D, m, N, fName);
  if (!fName.empty())
    f.open(fName.c_str());

  int verbose = 1;
  Processor *p = fName.empty() ? new Processor(std::cin, k0, k1, k2, D, m, N, verbose) :
                                 new Processor(f,        k0, k1, k2, D, m, N, verbose);
  int ret = p->infiniteLoop();
  p->output();

  f.close();
  delete p;
  return ret;
}

void usage()
{
  std::cerr << "Example: N = 4, m = 8, D = 5, k0 = 2, k1 = 2, k2 = 1\n";
  std::cerr << "  ./tom 4 8 5 2 2 1 ./gcc.txt > output-gcc\n";
  std::cerr << "  ./tom 4 8 5 2 2 1 < ./gcc.txt > output-gcc\n";
  std::cerr << "To try all sets of parameters:\n";
  std::cerr << "  ./tom ./gcc.txt\n";
}

void process_parameter(int argc, char** argv, int &k0, int &k1, int &k2, int &D, int &m, int &N, std::string& fName)
{
  if (argc < 7) {
    std::cerr << "There should be at least 6 parameters: N, m, D, k0, k1, k2\n";
    usage();
    exit(0);
  }
  N  = atoi(argv[1]);
  m  = atoi(argv[2]);
  D  = atoi(argv[3]);
  k0 = atoi(argv[4]);
  k1 = atoi(argv[5]);
  k2 = atoi(argv[6]);
  if (!(k0 > 0 && k1 > 0 && k2 > 0 && D > 0 && m > 0 && N > 0)) {
    std::cerr << "Check parameters: must satisfy k0 > 0 && k1 > 0 && k2 > 0 && d > 0 && m > 0 && N > 0\n";
    exit(0);
  }
  fName = argc >= 8 ? argv[7] : "";
}

void simulate(const std::string& fName, int k0, int k1, int k2, int D, int m, int N) 
{
  std::ifstream f(fName.c_str());
  if (!f.good()) {
    std::cerr << "Check file " << fName << "\n";
    usage();
    exit(0);
  }
  std::cerr << std::dec << "N = " << N << " m = " << m << " D = " << D 
              << " k0 = " << k0 << " k1 = " << k1 << " k2 = " << k2;
  Instruction::resetCounter();
  Processor p(f, k0, k1, k2, D, m, N, 0);
  p.infiniteLoop();
  f.close();
  std::cerr << std::dec << " ipc=" << p.ipc_ << "\n";

  std::ofstream out((fName+"-stats.txt").c_str(), std::ios::app);
  out << std::dec << N << "\t" << m << "\t" << D 
              << "\t" << k0 << "\t" << k1 << "\t" << k2 
              << "\t" << p.ipc_ << "\n";
  out.close();
}

void try_all(const std::string& fName) 
{
  std::ofstream out((fName+"-stats.txt").c_str());
  out.close();
  int Dlist[] = {1, 4};
  int mlist[] = {2, 8};
  int Nlist[] = {4, 8};
  for (int k0 = 1; k0 <= 2; k0++)
    for (int k1 = 1; k1 <= 2; k1++)
      for (int k2 = 1; k2 <= 2; k2++) {
        for (int id = 0; id < 2; id++) {
          int D = Dlist[id]*(k0+k1+k2);
          for (int im = 0; im < 2; im++) {
            int m = mlist[im];
            if (m*(k0+k1+k2) < D) continue;
            for (int in = 0; in < 2; in++) {
              int N = Nlist[in];
//              if (N > D) continue;
              simulate(fName, k0, k1, k2, D, m, N);
            }
          }
        }
      }
}
